package com.boot.springBoot.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import lombok.extern.slf4j.Slf4j;
import org.springframework.context.annotation.Scope;

/**
 * 
    * @ClassName: AlgorithmOffer  
    * @Description: TODO( 给定一组数字，以及一个数字k，确定这组数字中，是否存在任意两个数字，其相加之和等于k 
    * @author ysp  
    * @date 2019年5月13日  
    *
 */
@Slf4j
@Scope()
public class AlgorithmOffer {
		
	/**
	 * 给定一个数组
	 */
	private static int[] array = {2,3,5,4,9,12,14,22,8,30,18,20,10,30,50,80,40,60,100};
	
	
	private static int index = array.length;
	
	/**
	 * 这个是我初步的实现 两个for嵌套搞定      时间复杂度为O（n）= array.length^2     暂定1.0版
	 * 				
	    * @Title: getAddFirst  
	    * @Description: TODO(1.0)  
	    * @param     参数  
	    * @return void    返回类型  
	    * @throws
	 */
	public static boolean getAddFirst(int k) {
		long start = System.currentTimeMillis();
		for (int i = 0; i < index-1; i++) {
			int x = array[i];
			for (int j = 1; j < index; j++) {
				int y = array[j];
				if(x+y == k) {
					log.info("获取的x:{},y:{}",x,y);
					getTime(start);
					return true;
				}else {

				}
			}
			
		}
		getTime(start);
		return false;
	}
	
	/**
	 *  由于算法是计算两数之和等于k  假设想x，y 则有 x+y=k 估也有x = k-y或者y=k-x 只要确定了一个剩下的就可以是否被包含 就ok了
	 *  接下来，我们只需要遍历array一次。
		如果array[i]已经和map中的元素相符，就说明array[i]和我们之前遍历到的某一个元素恰好是相加为k的“一对儿”，算法直接返回true。
		如果不相符，那么我们就把k-array[i]放进map中去，期待接下来遍历到的元素能够和k-array[i]相符。
	    * @Title: getAddSecond  
	    * @Description: TODO(2.0)  
	    * @param     参数  
	    * @return void    返回类型  
	    * @throws
	 */
	
	public static boolean getAddSecond(int k) {
		long start = System.currentTimeMillis();
		Map< Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < index; i++) {
			if(map.containsValue(array[i])) {
				log.info("获取的x:{},y:{}",k-array[i],array[i]);
				getTime(start);
//				return true;
			}else {
				map.put(i, k-array[i]);
			}
		}
		map.forEach((n,v) -> {
			System.out.println("k=="+n+",v=="+v);
		});
		//耗时
		getTime(start);
		return false;
	}
	
	/**
	 * 
	    * @Title: gettime  
	    * @Description: TODO(计算算法执行时间)  
	    * @param @param start    参数  
	    * @return void    返回类型  
	    * @throws
	 */
	public static void getTime(long start) {
		long end = System.currentTimeMillis();
		log.info("该算法用时：{} 秒",(end - start)/1000.0);
	}
	
	public static void main(String[] args) {
		log.info("执行结果：{}",getAddFirst(30));
		log.info("执行结果：{}",getAddSecond(30));
//		Arrays.asList(array);
//		int x = 8,y= 4;
//		左移是变大了 乘法  右移变小了除法 2的次方 二进制
//		log.info("获取的x*y={}",x*y);
//		log.info("获取的x/y={}",x>>3);
//		log.info("获取的x/y={}",x/y);
//		log.info("获取的x*y={}",x<<2);
	}
	
}
